/**
 * @file BinaryTree.h
 * @author 张奕欣 3190105655 (3190105655@zju.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-11-04
 * 
 * @copyright Copyright (c) 2022
 * 
 */


// ******************PUBLIC OPERATIONS*********************
// void insert( x )         --> Insert x
// void remove( x )         --> Remove x
// bool contains( x )       --> Return true if x is present
// void PreOrderTraverse()  --> print the tree in pre order
// void InOrderTraverse()   --> print the tree in in order
// void PostOrderTraverse() --> print the tree in post order


#include <iostream>

/**
 * @brief Node class
 * 
 * @tparam Comparable 
 */
template<typename Comparable>
class Node
{
private:
    Comparable element; // elements saved in the tree
    Node *left; // left child
    Node *right; // right child
public:
    /**
     * @brief Get the Element object
     * 
     * @return Comparable 
     */
    virtual Comparable getElement() const = 0;
    /**
     * @brief Set the Element object
     * 
     * @param _val (left value)
     */
    virtual void setElement(Comparable &_val) = 0;
    /**
     * @brief Set the Element object
     * 
     * @param _val (right value)
     */
    virtual void setElement(Comparable &&_val) = 0;
};

/**
 * @brief  Tree class
 * 
 * @tparam Comparable 
 */
template<typename Comparable>
class Tree
{
public:
    /**
     * @brief insert an element into the tree
     * 
     * @param _val (left value)
     */
    virtual void insert(Comparable &_val) = 0;
    /**
     * @brief insert an element into the tree
     * 
     * @param _val (right value)
     */
    virtual void insert(Comparable &&_val) = 0;
    /**
     * @brief remove an element from the tree
     * 
     * @param _val the removed element
     */
    virtual void remove(Comparable _val) = 0;
    /**
     * @brief whether an element exists in the tree
     * 
     * @param _val the element 
     * @return true 
     * @return false 
     */
    bool contains(Comparable _val) = 0;
};

template<typename Comparable>
class BinaryTree : public Tree<Comparable>
{
private:
    Node<Comparable> *root; // root of the BinaryTree
public:

    virtual Comparable getElement() const;
    virtual void setElement(Comparable &_val){};
    virtual void setElement(Comparable &&_val){};

    virtual void insert(Comparable &_val){};	
    virtual void insert(Comparable &&_val){};
    virtual void remove(Comparable _val){};
    bool contains(Comparable _val){};

    /**
     * @brief print the tree in pre order
     * 
     * @param Node 
     */
    void PreOrderTraverse(Node *Node){};
    /**
     * @brief print the tree in In order
     * 
     * @param Node 
     */
    void InOrderTraverse(Node *Node){};
    /**
     * @brief print the tree in Postorder
     * 
     * @param Node 
     */
    void PostOrderTraverse(Node *Node){};

};